From 40fd42e81b9f65c7f573f3bd4c8c4d04e6f57878 Mon Sep 17 00:00:00 2001 From: "gm281@tetrapod.cl.cam.ac.uk" Date: Thu, 23 Sep 2004 19:15:34 +0000 Subject: [PATCH] bitkeeper revision 1.1159.85.1 (415320d6BPEnNqrgMXU8P8HlO9L5Kw) Atropos scheduler modified to conform to the new interfaces, debugged not to schedule idle tasks while other are present --- BitKeeper/etc/logging_ok | 1 + xen/common/sched_atropos.c | 346 +++++++++++++++++++++++-------------- 2 files changed, 213 insertions(+), 134 deletions(-) diff --git a/BitKeeper/etc/logging_ok b/BitKeeper/etc/logging_ok index 519c80013f..125ee3ffd9 100644 --- a/BitKeeper/etc/logging_ok +++ b/BitKeeper/etc/logging_ok @@ -13,6 +13,7 @@ cl349@freefall.cl.cam.ac.uk cl349@labyrinth.cl.cam.ac.uk djm@kirby.fc.hp.com gm281@boulderdash.cl.cam.ac.uk +gm281@tetrapod.cl.cam.ac.uk iap10@freefall.cl.cam.ac.uk iap10@labyrinth.cl.cam.ac.uk iap10@nidd.cl.cam.ac.uk diff --git a/xen/common/sched_atropos.c b/xen/common/sched_atropos.c index 53e4519b9f..f9229528fe 100644 --- a/xen/common/sched_atropos.c +++ b/xen/common/sched_atropos.c @@ -23,26 +23,17 @@ #include #include -/* - * KAF -- Atropos is broken by the new scheduler interfaces. - * It'll need fixing to get rid of use of ATROPOS_TASK__* - */ -#ifdef KAF_KILLED - #define ATROPOS_TASK_UNBLOCKED 16 #define ATROPOS_TASK_WAIT 32 - -#define Activation_Reason_Allocated 1 -#define Activation_Reason_Preempted 2 -#define Activation_Reason_Extra 3 +#define ATROPOS_TASK_BLOCKED 48 /* Atropos-specific per-domain data */ struct at_dom_info { /* MAW Xen additions */ struct domain *owner; /* the domain this data belongs to */ + struct list_head run_list; /* runqueue */ struct list_head waitq; /* wait queue */ - int reason; /* reason domain was last scheduled */ /* (what remains of) the original fields */ @@ -57,26 +48,59 @@ struct at_dom_info s_time_t latency; /* Unblocking latency */ int xtratime; /* Prepared to accept extra time? */ + int state; /* Keeps Atropos domain state */ }; /* Atropos-specific per-CPU data */ struct at_cpu_info { + spinlock_t runq_lock; + struct list_head runq; /* run queue */ + spinlock_t waitq_lock; struct list_head waitq; /* wait queue*/ }; #define DOM_INFO(_p) ((struct at_dom_info *)((_p)->sched_priv)) -#define CPU_INFO(_c) ((struct at_cpu_info *)((_c).sched_priv)) -#define WAITQ(cpu) (&CPU_INFO(schedule_data[cpu])->waitq) -#define RUNQ(cpu) (&schedule_data[cpu].runqueue) +#define CPU_INFO(_c) ((struct at_cpu_info *)((schedule_data[_c]).sched_priv)) +#define WAITQ(cpu) (&CPU_INFO(cpu)->waitq) +#define RUNQ(cpu) (&CPU_INFO(cpu)->runq) +#define RUNLIST(_d) (&DOM_INFO(_d)->run_list) #define BESTEFFORT_QUANTUM MILLISECS(5) +static void at_dump_cpu_state(int cpu); + /* SLAB cache for struct at_dom_info objects */ static xmem_cache_t *dom_info_cache; +/* + * Wrappers for run-queue management. Must be called with the run_lock + * held. + */ +static inline void __add_to_runqueue_head(struct domain *d) +{ + list_add(RUNLIST(d), RUNQ(d->processor)); +} + +static inline void __add_to_runqueue_tail(struct domain *d) +{ + list_add_tail(RUNLIST(d), RUNQ(d->processor)); +} + +static inline void __del_from_runqueue(struct domain *d) +{ + struct list_head *runlist = RUNLIST(d); + list_del(runlist); + runlist->next = NULL; +} + +static inline int __task_on_runqueue(struct domain *d) +{ + return (RUNLIST(d))->next != NULL; +} + /** calculate the length of a linked list */ static int q_len(struct list_head *q) @@ -114,15 +138,17 @@ static inline struct domain *waitq_el(struct list_head *l) static void requeue(struct domain *sdom) { struct at_dom_info *inf = DOM_INFO(sdom); - struct list_head *prev = WAITQ(sdom->processor); + struct list_head *prev; struct list_head *next; - if(sdom->state == ATROPOS_TASK_WAIT || - sdom->state == ATROPOS_TASK_UNBLOCKED ) - { - /* insert into ordered wait queue */ + if(!domain_runnable(sdom)) return; + + if(inf->state == ATROPOS_TASK_WAIT || + inf->state == ATROPOS_TASK_UNBLOCKED) + { prev = WAITQ(sdom->processor); + list_for_each(next, WAITQ(sdom->processor)) { struct at_dom_info *i = @@ -144,16 +170,17 @@ static void requeue(struct domain *sdom) else if ( domain_runnable(sdom) ) { /* insert into ordered run queue */ + prev = RUNQ(sdom->processor); list_for_each(next, RUNQ(sdom->processor)) { - struct domain *p = list_entry(next, struct domain, + struct at_dom_info *p = list_entry(next, struct at_dom_info, run_list); - if( DOM_INFO(p)->deadline > inf->deadline || is_idle_task(p) ) + if( p->deadline > inf->deadline || is_idle_task(p->owner) ) { - __list_add(&sdom->run_list, prev, next); + __list_add(&inf->run_list, prev, next); break; } @@ -161,12 +188,27 @@ static void requeue(struct domain *sdom) } if ( next == RUNQ(sdom->processor) ) - list_add_tail(&sdom->run_list, RUNQ(sdom->processor)); + list_add_tail(&inf->run_list, RUNQ(sdom->processor)); + + } /* silently ignore tasks in other states like BLOCKED, DYING, STOPPED, etc * - they shouldn't be on any queue */ } +/** at_alloc_task - allocate private info for a task */ +static int at_alloc_task(struct domain *p) +{ + ASSERT(p != NULL); + + p->sched_priv = xmem_cache_alloc(dom_info_cache); + if( p->sched_priv == NULL ) + return -1; + + return 0; +} + + /* prepare a task to be added to scheduling */ static void at_add_task(struct domain *p) { @@ -199,14 +241,15 @@ static void at_add_task(struct domain *p) DOM_INFO(p)->slice = MILLISECS(10); DOM_INFO(p)->latency = SECONDS(10); DOM_INFO(p)->xtratime = 1; - DOM_INFO(p)->deadline = now + SECONDS(10); + DOM_INFO(p)->deadline = now; +// DOM_INFO(p)->deadline = now + SECONDS(10); DOM_INFO(p)->prevddln = 0; } + INIT_LIST_HEAD(&(DOM_INFO(p)->run_list)); INIT_LIST_HEAD(&(DOM_INFO(p)->waitq)); } - /** * dequeue - remove a domain from any queues it is on. * @sdom: the task to remove @@ -214,19 +257,16 @@ static void at_add_task(struct domain *p) static void dequeue(struct domain *sdom) { struct at_dom_info *inf = DOM_INFO(sdom); - + ASSERT(sdom->domain != IDLE_DOMAIN_ID); /* just delete it from all the queues! */ list_del(&inf->waitq); INIT_LIST_HEAD(&inf->waitq); + if(__task_on_runqueue(sdom)) __del_from_runqueue(sdom); - - sdom->run_list.next = NULL; - sdom->run_list.prev = NULL; - } @@ -254,44 +294,64 @@ static void unblock(struct domain *sdom) { s_time_t time = NOW(); struct at_dom_info *inf = DOM_INFO(sdom); - + dequeue(sdom); /* We distinguish two cases... short and long blocks */ - if ( inf->deadline < time ) { /* Long blocking case */ - /* The sdom has passed its deadline since it was blocked. - Give it its new deadline based on the latency value. */ - inf->prevddln = time; + /* The sdom has passed its deadline since it was blocked. + Give it its new deadline based on the latency value. */ + inf->prevddln = time; /* Scale the scheduling parameters as requested by the latency hint. */ - inf->deadline = time + inf->latency; + inf->deadline = time + inf->latency; inf->slice = inf->nat_slice / ( inf->nat_period / inf->latency ); inf->period = inf->latency; - inf->remain = inf->slice; + inf->remain = inf->slice; } - else + else { /* Short blocking case */ - /* We leave REMAIN intact, but put this domain on the WAIT - queue marked as recently unblocked. It will be given - priority over other domains on the wait queue until while - REMAIN>0 in a generous attempt to help it make up for its - own foolishness. */ - if(inf->remain > 0) - sdom->state = ATROPOS_TASK_UNBLOCKED; + /* We leave REMAIN intact, but put this domain on the WAIT + queue marked as recently unblocked. It will be given + priority over other domains on the wait queue until while + REMAIN>0 in a generous attempt to help it make up for its + own foolishness. */ + if(inf->remain > 0) + inf->state = ATROPOS_TASK_UNBLOCKED; else - sdom->state = ATROPOS_TASK_WAIT; + inf->state = ATROPOS_TASK_WAIT; } requeue(sdom); +} + + +static int at_init_idle_task(struct domain *p) +{ + if(at_alloc_task(p) < 0) return -1; + + at_add_task(p); + + dequeue(p); + requeue(p); + + return 0; +} + +static void block(struct domain* sdom) +{ + DOM_INFO(sdom)->state = ATROPOS_TASK_BLOCKED; + dequeue(sdom); + requeue(sdom); } + /** * ATROPOS - main scheduler function */ @@ -301,13 +361,13 @@ task_slice_t ksched_scheduler(s_time_t time) s_time_t newtime; s_time_t ranfor; /* How long the domain ran */ struct domain *sdom; /* tmp. scheduling domain */ - int reason; /* reason for reschedule */ int cpu = cur_sdom->processor; /* current CPU */ struct at_dom_info *cur_info; static unsigned long waitq_rrobin = 0; int i; task_slice_t ret; + cur_info = DOM_INFO(cur_sdom); ASSERT( cur_sdom != NULL); @@ -333,36 +393,35 @@ task_slice_t ksched_scheduler(s_time_t time) dequeue(cur_sdom); if ( domain_runnable(cur_sdom) || - (cur_sdom->state == ATROPOS_TASK_UNBLOCKED) ) + (cur_info->state == ATROPOS_TASK_UNBLOCKED) ) { - /* In this block, we are doing accounting for an sdom which has - been running in contracted time. Note that this could now happen - even if the domain is on the wait queue (i.e. if it blocked) */ + /* In this block, we are doing accounting for an sdom which has + been running in contracted time. Note that this could now happen + even if the domain is on the wait queue (i.e. if it blocked) */ - /* Deduct guaranteed time from the domain */ - cur_info->remain -= ranfor; + /* Deduct guaranteed time from the domain */ + cur_info->remain -= ranfor; - /* If guaranteed time has run out... */ - if ( cur_info->remain <= 0 ) + /* If guaranteed time has run out... */ + if ( cur_info->remain <= 0 ) { - /* Move domain to correct position in WAIT queue */ + /* Move domain to correct position in WAIT queue */ /* XXX sdom_unblocked doesn't need this since it is already in the correct place. */ - cur_sdom->state = ATROPOS_TASK_WAIT; - } + cur_info->state = ATROPOS_TASK_WAIT; + } } requeue(cur_sdom); - deschedule_done: - +deschedule_done: /***************************** * * We have now successfully descheduled the current sdom. * The next task is the allocate CPU time to any sdom it is due to. * - ****************************/ + ****************************/ cur_sdom = NULL; /***************************** @@ -371,13 +430,14 @@ task_slice_t ksched_scheduler(s_time_t time) * period deadline. If necessary, move them to run queue. * ****************************/ + while(!list_empty(WAITQ(cpu)) && - DOM_INFO(sdom = waitq_el(WAITQ(cpu)->next))->deadline <= time ) { - - struct at_dom_info *inf = DOM_INFO(sdom); + DOM_INFO(sdom = waitq_el(WAITQ(cpu)->next))->deadline <= time ) + { + struct at_dom_info *inf = DOM_INFO(sdom); dequeue(sdom); - + if ( inf->period != inf->nat_period ) { /* This domain has had its parameters adjusted as a result of @@ -392,22 +452,22 @@ task_slice_t ksched_scheduler(s_time_t time) } } - /* Domain begins a new period and receives a slice of CPU - * If this domain has been blocking then throw away the - * rest of it's remain - it can't be trusted */ - if (inf->remain > 0) - inf->remain = inf->slice; - else - inf->remain += inf->slice; + /* Domain begins a new period and receives a slice of CPU + * If this domain has been blocking then throw away the + * rest of it's remain - it can't be trusted */ + if (inf->remain > 0) + inf->remain = inf->slice; + else + inf->remain += inf->slice; - inf->prevddln = inf->deadline; - inf->deadline += inf->period; + inf->prevddln = inf->deadline; + inf->deadline += inf->period; if ( inf->remain <= 0 ) - sdom->state = ATROPOS_TASK_WAIT; + inf->state = ATROPOS_TASK_WAIT; - /* Place on the appropriate queue */ - requeue(sdom); + /* Place on the appropriate queue */ + requeue(sdom); } /***************************** @@ -421,13 +481,11 @@ task_slice_t ksched_scheduler(s_time_t time) ****************************/ /* we guarantee there's always something on the runqueue */ - cur_sdom = list_entry(RUNQ(cpu)->next, - struct domain, run_list); + cur_info = list_entry(RUNQ(cpu)->next, + struct at_dom_info, run_list); - cur_info = DOM_INFO(cur_sdom); + cur_sdom = cur_info->owner; newtime = time + cur_info->remain; - reason = (cur_info->prevddln > cur_sdom->lastschd) ? - Activation_Reason_Allocated : Activation_Reason_Preempted; /* MAW - the idle domain is always on the run queue. We run from the * runqueue if it's NOT the idle domain or if there's nothing on the wait @@ -436,12 +494,13 @@ task_slice_t ksched_scheduler(s_time_t time) { struct list_head *item; - /* Try running a domain on the WAIT queue - this part of the - scheduler isn't particularly efficient but then again, we - don't have any guaranteed domains to worry about. */ + /* Try running a domain on the WAIT queue - this part of the + scheduler isn't particularly efficient but then again, we + don't have any guaranteed domains to worry about. */ - /* See if there are any unblocked domains on the WAIT - queue who we can give preferential treatment to. */ + /* See if there are any unblocked domains on the WAIT + queue who we can give preferential treatment to. */ + list_for_each(item, WAITQ(cpu)) { struct at_dom_info *inf = @@ -449,23 +508,24 @@ task_slice_t ksched_scheduler(s_time_t time) sdom = inf->owner; - if (sdom->state == ATROPOS_TASK_UNBLOCKED) { - cur_sdom = sdom; - cur_info = inf; - newtime = time + inf->remain; - reason = Activation_Reason_Preempted; - goto found; + if (inf->state == ATROPOS_TASK_UNBLOCKED) + { + cur_sdom = sdom; + cur_info = inf; + newtime = time + inf->remain; + goto found; + } } - } /* init values needed to approximate round-robin for slack time */ i = 0; if ( waitq_rrobin >= q_len(WAITQ(cpu))) waitq_rrobin = 0; - /* Last chance: pick a domain on the wait queue with the XTRA - flag set. The NEXT_OPTM field is used to cheaply achieve - an approximation of round-robin order */ + + /* Last chance: pick a domain on the wait queue with the XTRA + flag set. The NEXT_OPTM field is used to cheaply achieve + an approximation of round-robin order */ list_for_each(item, WAITQ(cpu)) { struct at_dom_info *inf = @@ -473,11 +533,11 @@ task_slice_t ksched_scheduler(s_time_t time) sdom = inf->owner; - if (inf->xtratime && i >= waitq_rrobin) { + if (inf->xtratime && i >= waitq_rrobin) + { cur_sdom = sdom; cur_info = inf; newtime = time + BESTEFFORT_QUANTUM; - reason = Activation_Reason_Extra; waitq_rrobin = i + 1; /* set this value ready for next */ goto found; } @@ -502,7 +562,7 @@ task_slice_t ksched_scheduler(s_time_t time) /* exhausted its time, cut short the time allocation */ if (!list_empty(WAITQ(cpu))) { - newtime = MIN(newtime, + newtime = MIN(newtime, DOM_INFO(waitq_el(WAITQ(cpu)->next))->deadline); } @@ -512,9 +572,6 @@ task_slice_t ksched_scheduler(s_time_t time) ret.task = cur_sdom; ret.time = newtime - time; - cur_sdom->min_slice = newtime - time; - DOM_INFO(cur_sdom)->reason = reason; - TRACE_1D(0, cur_sdom->domain); return ret; @@ -531,8 +588,10 @@ static int at_init_scheduler() schedule_data[i].sched_priv = xmalloc(sizeof(struct at_cpu_info)); if ( schedule_data[i].sched_priv == NULL ) return -1; - WAITQ(i)->next = WAITQ(i); - WAITQ(i)->prev = WAITQ(i); + INIT_LIST_HEAD(WAITQ(i)); + INIT_LIST_HEAD(RUNQ(i)); + spin_lock_init(&CPU_INFO(i)->runq_lock); + spin_lock_init(&CPU_INFO(i)->waitq_lock); } dom_info_cache = xmem_cache_create("Atropos dom info", @@ -542,13 +601,6 @@ static int at_init_scheduler() return 0; } -/* dump relevant per-cpu state for a run queue dump */ -static void at_dump_cpu_state(int cpu) -{ - printk("Waitq len: %d Runq len: %d ", - q_len(WAITQ(cpu)), - q_len(RUNQ(cpu))); -} /* print relevant per-domain info for a run queue dump */ static void at_dump_runq_el(struct domain *p) @@ -558,6 +610,51 @@ static void at_dump_runq_el(struct domain *p) } +/* dump relevant per-cpu state for a run queue dump */ +static void at_dump_cpu_state(int cpu) +{ + struct list_head *list, *queue; + int loop = 0; + struct at_dom_info *d_inf; + struct domain *d; + + queue = RUNQ(cpu); + printk("\nRUNQUEUE rq %lx n: %lx, p: %lx\n", (unsigned long)queue, + (unsigned long) queue->next, (unsigned long) queue->prev); + + list_for_each ( list, queue ) + { + d_inf = list_entry(list, struct at_dom_info, run_list); + d = d_inf->owner; + printk("%3d: %d has=%c ", loop++, d->domain, + test_bit(DF_RUNNING, &d->flags) ? 'T':'F'); + at_dump_runq_el(d); + printk("c=0x%X%08X\n", (u32)(d->cpu_time>>32), (u32)d->cpu_time); + printk(" l: %lx n: %lx p: %lx\n", + (unsigned long)list, (unsigned long)list->next, + (unsigned long)list->prev); + } + + + queue = WAITQ(cpu); + printk("\nWAITQUEUE rq %lx n: %lx, p: %lx\n", (unsigned long)queue, + (unsigned long) queue->next, (unsigned long) queue->prev); + + list_for_each ( list, queue ) + { + d_inf = list_entry(list, struct at_dom_info, waitq); + d = d_inf->owner; + printk("%3d: %d has=%c ", loop++, d->domain, + test_bit(DF_RUNNING, &d->flags) ? 'T':'F'); + at_dump_runq_el(d); + printk("c=0x%X%08X\n", (u32)(d->cpu_time>>32), (u32)d->cpu_time); + printk(" l: %lx n: %lx p: %lx\n", + (unsigned long)list, (unsigned long)list->next, + (unsigned long)list->prev); + } + +} + /* set or fetch domain scheduling parameters */ static int at_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) { @@ -585,22 +682,6 @@ static int at_adjdom(struct domain *p, struct sched_adjdom_cmd *cmd) return 0; } - -/** at_alloc_task - allocate private info for a task */ -static int at_alloc_task(struct domain *p) -{ - ASSERT(p != NULL); - - p->sched_priv = xmem_cache_alloc(dom_info_cache); - if( p->sched_priv == NULL ) - return -1; - - memset(p->sched_priv, 0, sizeof(struct at_dom_info)); - - return 0; -} - - /* free memory associated with a task */ static void at_free_task(struct domain *p) { @@ -627,23 +708,20 @@ static int at_prn_state(int state) return ret; } - -#endif /* KAF_KILLED */ struct scheduler sched_atropos_def = { .name = "Atropos Soft Real Time Scheduler", .opt_name = "atropos", .sched_id = SCHED_ATROPOS, -#ifdef KAF_KILLED .init_scheduler = at_init_scheduler, + .init_idle_task = at_init_idle_task, .alloc_task = at_alloc_task, .add_task = at_add_task, .free_task = at_free_task, - .wake_up = unblock, + .wake = unblock, + .sleep = block, .do_schedule = ksched_scheduler, .adjdom = at_adjdom, .dump_cpu_state = at_dump_cpu_state, - .dump_runq_el = at_dump_runq_el, .prn_state = at_prn_state, -#endif /* KAF_KILLED */ }; -- 2.30.2